1. 문제 22862번: 가장 긴 짝수 연속한 부분 수열 (large) (acmicpc.net) 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 2. 풀이 투 포인터로는 원소를 포함시키면서 가장 긴 수열을 찾아가는 건데 어떻게 해야 최대 K번 원소를 삭제하면서 가장 긴 짝수만 포함된 연속 부분 수열을 찾을 수 있을까? 생각보다 간단하다 투 포인터 i,j로 범위를 확장해나가는데, j번 원소가 홀수라면, K값을 감소시키고 길이를 증가시키지 않는다. K가 홀수를 포함시킬 수 있는 최대 기회라고 생각한다면, 원소를 실제로 삭제하지 않고도 마치 삭제한..
1. 문제 2018번: 수들의 합 5 (acmicpc.net) 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 2. 풀이 이전에 풀이한 방식대로, 포인터 i,j를 잡고 구간 [i,j]의 합이 N이 되는지 아닌지를 검사하면 된다 자연수 N이 연속된 자연수의 합으로 나타낼려면 결국 N보다 작거나 같은 자연수의 합으로 나타낼 수밖에 없다 그러므로 1부터 n까지 natural이라는 배열을 만들었고 (정렬은 왜 한건지 모르겠지만..) 포인터 i,j를 잡은 다음, 초기값 natural[0]로 잡는다..
1. 문제 14246번: K보다 큰 구간 (acmicpc.net) 14246번: K보다 큰 구간 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오. www.acmicpc.net 2. 풀이 첫번째 핵심 두개의 포인터 i,j를 두고 i~j까지의 합이 k보다 작다면, 끝 포인터 j를 1칸 늘린다. 모든 수가 자연수이기 때문에 끝 포인터 j를 1칸 늘리면 구간 합이 증가하게 된다 ------------------------------------------------------------------------------------------------------------ 두번째 핵심 반대로 i~j까지의 합이 k보다 크다면, 그 순간 ..
1. 개요 이미 정렬되어 있는 2개의 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하라한다면 어떻게 해야할까 2. 알고리즘 2-1) 정렬된 리스트 A와 B를 입력받는다 2-2) 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리킨다 2-3) 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리킨다 2-4) A[i]와 B[j]중 더 작은 원소를 결과 리스트에 담는다 만약 A[i]가 더 작다면 i를 1 증가시킨다 B[j]가 더 작다면 j를 1 증가시킨다 2-5) 만약 i나 j가 가리키는 리스트의 길이를 넘어서는 경우, 남아있는 리스트의 원소를 모두 차례대로 담으면 된다 병합정렬이랑 똑같잖아? 3. 예시를 통해 이해하는 알고리즘 A = [1,3,5]이고 B=[2,4,6,8]일때, ..
1. 개요 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 예를 들어 한 반에 학생이 40명이 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤에 학생들을 순차적으로 지목한다고 하자 2,3,4,5,6,7번 학생을 지목해야할 때, 우리는 번호로 한명씩 부르기보다는, "2번부터 7번까지의 학생"이라고 부를 수도 있다. 이처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는, '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 2. 예시 - 특정한 합을 가지는 부분 연속 수열 찾기 문제 양의 정수로만 구성된 리스트가 주어질때, 그 부분 연속 수열중에서 특정한 합을 갖는 수열의 개수를 출력하는 문제를 생각해보자. 예..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
